package _10_图;

import java.util.LinkedList;
import java.util.Queue;

public class _547_省份数量 {

    int[] parents;

    // 广度优先搜索
    public int findCircleNum1(int[][] isConnected) {
        int province = isConnected.length;
        // 存放一个访问数组
        boolean[] visited = new boolean[province];
        int result = 0;
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < province; i++) {
            // 当前城市没有被访问过
            if (!visited[i]) {
                queue.offer(i);
                while (!queue.isEmpty()) {
                    int curProvince = queue.poll();
                    visited[curProvince] = true;
                    // 当前省份是否和其他省份存在连通分量
                    for (int j = 0; j < province; j++) {
                        if (j == curProvince) continue;
                        if (isConnected[curProvince][j] == 1 && !visited[j]) {
                            visited[j] = true;
                            queue.offer(j);
                        }
                    }
                }
                result++;
            }
        }
        return result;
    }

    // 深度优先搜索
    public int findCircleNum(int[][] isConnected) {
        int province = isConnected.length;
        // 存放一个访问数组
        boolean[] visited = new boolean[province];
        int result = 0;
        for (int i = 0; i < province; i++) {
            // 当前省份没有被访问过
            if (!visited[i]) {
                // 深度优先搜索，查看是否有与当前相连的连通分量
                dfs(isConnected, province, i, visited);
                result++;
            }
        }
        return result;
    }

    public void dfs(int[][] isConnected, int province, int i, boolean[] visited) {
        for (int j = 0; j < province; j++) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                visited[j] = true;
                // 查看是否还存在于当前省份放相连的连通分量
                dfs(isConnected, province, j, visited);
            }
        }
    }

    // 并查集
    public int findCircleNum2(int[][] isConnected) {
        // 初始化并查集数量
        int size = isConnected.length;
        // 初始化，父元素集合, 自己指向自己
        parents = new int[size];
        for (int i = 0; i < parents.length; i++) {
            parents[i] = i;
        }

        for (int i = 0; i < isConnected.length; i++) {
            for (int j = i + 1; j < isConnected[i].length; j++) {
                if (isConnected[i][j] == 1 && !isSame(i, j)) {
                    // 连接
                    union(i, j);
                }
            }
        }

        // 返回不重复元素元素
        int result = 0;
        for (int i = 1; i < parents.length; i++) {
            if (parents[i] == i) {
                result++;
            }
        }
        return result;
    }

    public int find(int v) {
        if (v != parents[v]) {
            parents[v] = find(parents[v]);
        }
        return parents[v];
    }

    public boolean isSame(int v1, int v2) {
        return find(v1) == find(v2);
    }

    public void union(int v1, int v2) {
        // 查找v1中的所有元素
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) return;
        parents[p1] = p2;
    }


}
